1. Field of the Invention
This invention relates in general to the field of memory management and memory system architectures in computer systems, and more specifically, to the organization of the address space around specific compressed memory data structures and a method and apparatus for managing the access to the memory.
2. Discussion of the Prior Art
Computer systems generally consist of one or more processors that execute program instructions stored within a memory medium. This mass storage medium is most often constructed of the lowest cost per bit, yet slowest storage technology, typically magnetic or optical media. To increase the system performance, a higher speed, yet smaller and more costly memory, known as the main memory, is first loaded with information from the mass storage for more efficient direct access by the processors.
Recently, cost reduced computer system architectures have been developed that more than double the effective size of the main memory by employing high speed compression/decompression hardware, based of common compression algorithms, in the path of information flow to and from the main memory. Processor access to main memory within these systems is performed indirectly through the compressor and decompressor apparatuses, both of which add significantly to the processor access latency costs.
Referring now to FIG. 1, a block diagram of a prior art computer system 100 is shown. The computer system includes one or more processors 101 connected to a common shared memory controller 102 that provides access to a system main memory 103. The shared memory controller contains a compressor 104 for compressing fixed size information blocks into as small a unit as possible for ultimate storage into the main memory, a decompressor 105 for reversing the compression operation after the stored information is later retrieved from the main memory. The processor data bus 108 is used for transporting uncompressed information between other processors and/or the shared memory controller. Information may be transferred to the processor data bus 108 from the main memory 103, either through or around the decompressor 105 via a multiplexor 111. Similarly, information may be transferred to the main memory 103 from the processor data bus 108 to the write buffer and then either through or around the compressor 104 via a multiplexor 112.
The main memory 103 is typically constructed of dynamic random access memory (DRAM) with access controlled by a memory controller 106. Scrub control hardware within the memory controller can periodically and sequentially read and write DRAM content through error detection and correction logic for the purpose of detecting and correcting bit errors that tend to accumulate in the DRAM. Addresses appearing on the processor address bus 107 are known as Real Addresses, and are understood and known to the programming environment. Addresses appearing on the main memory address bus 109 are known as Physical Addresses, and are used and relevant only between the memory controller and main memory DRAM. Memory Management Unit (MMU) hardware within the memory controller 106 is used to translate the real processor addresses to the virtual physical address space. This translation provides a means to allocate the physical memory in small increments for the purpose of efficiently storing and retrieving compressed and hence, variable size information.
The compressor 104 operates on a fixed size block of information, say 1024 bytes, by locating and replacing repeated byte strings within the block with a pointer to the first instance of a given string, and encoding the result according to a protocol. This scheme results in a variable size output block, ranging from just a few bytes to the original block size, when the compressor could not sufficiently reduce the starting block size to warrant compressing at all. The decompressor 105 functions by reversing the compressor operation by decoding resultant compressor output block to reconstruct the original information block by inserting byte strings back into the block at the position indicated by the noted pointers. Even in the very best circumstances, the compressor is generally capable of only xc2xc-xc2xd the data rate bandwidth of the surrounding system. The compression and decompression processes are naturally linear and serial too, implying quite lengthy memory access latencies through the hardware.
Referring to FIG. 2, there is shown a conventional partitioning scheme 200 for the main memory 103 (FIG. 1). The main memory 205 is a logical entity because it includes the processor(s) information as well as all the required data structures necessary to access the information. The logical main memory 205 is physically partitioned from the physical memory address space 206. In many cases the main memory partition 205 is smaller than the available physical memory to provide a separate region to serve as a cache with either an integral directory, or one that is implemented externally 212. It should be noted that when implemented, the cache storage may be implemented as a region 201 of the physical memory 206, a managed quantity of uncompressed sectors, or as a separate storage array. In any case, when implemented, the cache controller will request accesses to the main memory in a similar manner as a processor would if the cache were not present. Although it is typical for a large cache to be implemented between the processor(s) and main memory for the highest performance, it is not required, and is beyond the scope of the invention.
The logical main memory 205 is partitioned into the sector translation table 202, with the remaining memory being allocated to sector storage 203 which may contain compressed, uncompressed, free sector pointers, or any other information as long as it is organized into sectors 204. The sector translation table region size varies in proportion to the real address space size which is defined by a programmable register within the system.
Particularly, equation 1) governs the relation of the sector translation table region size as follows:                               sector_translation          ⁢          _table          ⁢          _size                =                                                            real_memory                ⁢                _size                                            compression_block                ⁢                _size                                      ·            translation_table                    ⁢          _entry          ⁢          _size                                    1        )            
Each entry is directly mapped to a fixed address range in the processor""s real address space, the request address being governed in accordance with equation 2) as follows:                               STT_entry          ⁢          _address                =                              (                                                            (                                      real_address                                          compression_block                      ⁢                      _size                                                        )                                ·                translation_table                            ⁢              _entry              ⁢              _size                        )                    +                      cache_region            ⁢            _size                                              2        )            
For example, a mapping may employ a 16 byte translation table entry to relocate a 1024 byte real addressed compression block, allocated as a quantity 256 byte sectors, each located at the physical memory address indicated by a 25-bit pointer stored within the table entry. The entry also contains attribute bits 208 that indicate the number of sector pointers that are valid, size, and possibly other information.
Every real address reference to the main memory causes memory controller to reference the translation table entry 207 corresponding to the real address block containing the request address. For read requests, the MMU decodes the attribute bits 208, extracts the valid pointer(s) 209 and requests the memory controller to read the information located at the indicated sectors 204 from the main memory sectored region 203. Similarly, write requests result in the MMU and memory controller performing the same actions, except information is written to the main memory. However, if a write request requires more sectors than are already valid in the translation table entry, then additional sectors need to be assigned to the table entry before the write may commence. Sectors are generally allocated from a list of unused sectors that is dynamically maintained as a stack or linked list of pointers stored in unused sectors. There are many possible variations on this translation scheme, but all involve a region of main memory mapped as a sector translation table and a region of memory mapped as sectors. Storage of these data structures in the DRAM based main memory provides the highest performance at the lowest cost, as well as ease of reverting the memory system into a typical direct mapped memory without compression and translation.
Large high speed cache memories are implemented between the processor and the compressor and decompressor hardware to reduce the frequency of processor references to the compressed memory to mitigate the effects the high compression/decompression latency. However, system performance can be further improved for certain memory access patterns and/or information structures that are insensitive to the benefits of the large cache. Therefore, the need has arisen for an improved method of information storage and access without significant cost or complexity, to minimize processor access latencies under certain conditions.
Computer systems that employ main memory compression achieve performance benefits when certain memory regions are segregated from the compressed memory and always remain uncompressed. This performance advantage results from the considerably lower access latency when memory references bypass the compression and decompression hardware and related address translation. Segregated regions may be implemented by simply defining regions where compression is disabled, but data is still stored in the compressed memory sectors, requiring a reference to a Sector Translation Table (STT) before an access may be serviced. Even cache structures that employ high speed directories are performance disadvantaged by the cache replacement overhead and algorithm, as well as the directory access overhead.
It is an object of the invention to provide a computer memory management system and methodology for partitioning a fixed size physical memory into regions including a relocated direct mapped uncompressed region that requires no Sector Translation Table (STT) or directory reference to service a processor access, thereby reducing memory latency to a minimum and fixed latency.
It is a further object of the invention to provide a method and apparatus for enabling user configuration of a computer main memory system into unique, logical partitions including a STT table region, an unsectored memory region and a sectored memory region of variable sizes.
It is another object of the invention to provide a computer memory system that comprises unique, logically partitioned regions including a STT table region, an unsectored memory region and a sectored memory region of variable sizes that is user configurable, whereby STT table entries map into sectored memory space in the sectored memory region and additional sectored memory space is extracted from the STT region at locations corresponding to locations allocated in the unsectored memory region.
According to the invention, there is provided a system and method for managing and logically partitioning physical main memory into three regions; the Sector Translation Table (STT), sectored memory, and uncompressed memory. These three regions are unified together to form a mapped memory available to the memory controller. The mapped memory space can xe2x80x9cfloatxe2x80x9d between the most significant SDRAM byte address (top) and the least significant SDRAM byte address (bottom) of the memory, as defined by Physical Memory Configuration Register(s). The physical memory is completely remapped (virtualized) from the real address space defined at the processor interface. The STT serves as the directory for the remapping of the compressed data. The uncompressed regions of real memory, defined by Compression Inhibit Range Register(s), are direct mapped into the uncompressed memory region of physical memory. These registers are configured by a system processor at system startup, and remain static throughout system operation.
The memory mapping scheme of the invention permits the STT and uncompressed memory regions to be referenced at an origin address at the logical bottom and top of the physical memory map, leaving the region between allocated regions as sectored memory. These regions may expand or contract depending on the memory configuration established by the user. With respect to the STT, as the addresses of memory locations within the unsectored memory region never use any sectors, then the direct mapped sector translation table entries represent xe2x80x9cholesxe2x80x9d within the table that are not used. These holes within the sector translation table may be used as additional sector storage for increases memory utilization. These locations are made available by placing the addresses to the storage on a sector free list at system start-up.
Advantageously, the system of the invention permits computers to be constructed with hardware compressed memory systems without wasted memory or the side effects of high and variable latency access to critical memory references, for example; video, translation tables, BIOS, device driver, or interrupt service program code or data.